/**
 * @author SaoE
 * @date 2025/2/21 15:48
 */
public class _437 {
    int res = 0;

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        // 外层递归：遍历每个节点
        pathSum(root.left, targetSum);  // 遍历左子树
        pathSum(root.right, targetSum); // 遍历右子树
        // 内层递归：从当前节点开始计算路径和
        dfs(root, targetSum, 0L);       // 使用 long 类型避免溢出
        return res;
    }

    public void dfs(TreeNode root, int targetSum, long sum) {
        if (root == null) {
            return;
        }
        sum += root.val; // 更新路径和
        if (sum == targetSum) {
            res++; // 找到一条满足条件的路径
        }
        // 继续向下遍历
        dfs(root.left, targetSum, sum);
        dfs(root.right, targetSum, sum);
    }

    public static void main(String[] args) {
        _437 a = new _437();
        // [1,null,2,null,3,null,4,null,5]
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.right = new TreeNode(3);
        root.right.right.right = new TreeNode(4);
        root.right.right.right.right = new TreeNode(5);
        System.out.println(a.pathSum(root, 3));
    }
}
